package HashTable;

import java.util.*;

public class _447_NumberofBoomerangs {
    //use hashmap
    //Time Limit Exceeded
    public int numberOfBoomerangs0(int[][] points) {
        int count = 0;
        for(int i=0;i<points.length;i++) {
            for(int j=0;j<points.length;j++) {
                if (j != i) {
                    for(int k=0;k<points.length;k++) {
                        int x = points[k][0];
                        int y = points[k][1];
                        if (k != j && k != i) {
                            int x1 = Math.abs(x - points[i][0]);
                            int x2 = Math.abs(x - points[j][0]);
                            int y1 = Math.abs(y - points[i][1]);
                            int y2 = Math.abs(y - points[j][1]);
                            if ((x1 * x1 + y1 * y1) == (x2 * x2 + y2 * y2)) {
                                count++;
                            }
                        }
                    }
                }
            }
        }
        return count;
    }

    //hint:use hashMap to store every distance's length and count,then use permutation and combination's method to calculate
    //the count
    public int numberOfBoomerangs(int[][] points) {
        int count = 0;
        for(int i=0;i<points.length;i++) {
            Map<Double,Integer> tempMap = new HashMap<>();
            for(int j=0;j<points.length;j++) {
                double distance = Math.pow(Math.abs(points[i][0] - points[j][0]), 2) + Math.pow(Math.abs(points[i][1] - points[j][1]), 2);
                if (tempMap.containsKey(distance)) {
                    int preCount = tempMap.get(distance);
                    count-=preCount*(preCount-1);
                    int nowCount = preCount+1;
                    tempMap.put(distance, nowCount);
                    count +=nowCount*(nowCount-1);
                } else {
                    tempMap.put(distance,1);
                }
            }
        }
        return count;
    }
    //doesn't consider the situation that different node which have a same x value
//    public int numberOfBoomerangs(int[][] points) {
//        int count = 0;
//        Map<Double, List<Double>> map = new HashMap<>();
//        for(int i=0;i<points.length;i++) {
//            Double x = new Double(points[i][0]);
//            Double y = new Double(points[i][1]);
//            if (map.containsKey(x)) {
//                map.get(x).add(y);
//            } else {
//                List<Double> list = new ArrayList<>();
//                list.add(y);
//                map.put(x, list);
//            }
////            System.out.println(map.toString());
//        }
//        for (Map.Entry<Double, List<Double>> m : map.entrySet()) {
//            for (Map.Entry<Double, List<Double>> n : map.entrySet()) {
//                if (m.getKey() != n.getKey()) {
//                    for (Double mi : m.getValue()) {
//                        for (Double ni : n.getValue()) {
//                            for (Map.Entry<Double, List<Double>> middle : map.entrySet()) {
//                                if (middle != m && middle != n) {
//
//                                }
//                            }
//
//                        }
//                    }
//                }
//            }
//        }
//        return count;
//    }
}
